package com.yoshino.leetcode.oneHundred.twentyfiveth;

import java.util.Stack;

class Solution {
    public int[] spiralOrder2(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        int m = matrix.length, n = matrix[0].length, ind = 0;
        boolean[][] isVisted = new boolean[m][n];
        int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
        int[] res = new int[m * n];
        for (int i = 0, j = 0, tot = 0; tot < n * m; tot++) {
            res[tot] = matrix[i][j];
            isVisted[i][j] = true;
            int nexi = i + dir[ind][0], nexj = j + dir[ind][1];
            if (nexi < 0 || nexi == m || nexj < 0 || nexj == n || isVisted[nexi][nexj]) {
                ind = (ind + 1) % 4;
            }
            i += dir[ind][0];
            j += dir[ind][1];
        }
        return res;
    }
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        int m = matrix.length, n = matrix[0].length, idx = 0;
        int[] res = new int[m * n];
        int left = 0, top = 0, right = n - 1, bottom = m - 1;
        while (true) {
            //从左往右走
            for (int i = left; i <= right; i++) {
                res[idx++] = matrix[top][i];
            }
            if (++top > bottom) {
                break;
            }
            //从上往下走
            for (int i = top; i <= bottom; i++) {
                res[idx++] = matrix[i][right];
            }
            if (--right < left) {
                break;
            }
            //从右往左走
            for (int i = right; i >= left; i--) {
                res[idx++] = matrix[bottom][i];
            }
            if (--bottom < top) {
                break;
            }
            //从下往上走
            for (int i = bottom; i >= top; i--) {
                res[idx++] = matrix[i][left];
            }
            if (++left > right) {
                break;
            }
        }
        return res;

    }

    public boolean validateStackSequences2(int[] pushed, int[] popped) {
        if (pushed.length == 0) {
            return true;
        }
        Stack<Integer> stack = new Stack<>();
        boolean res = true;
        int i = 0, j = 0;
        for (; i < pushed.length; i++) {
            if (stack.isEmpty() || stack.peek() != popped[j]) {
                stack.push(pushed[i]);
            }
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return i == j;
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int i = 0, j = 0;
        for (int p : pushed) {
            pushed[i] = p;
            while (i >= 0 && pushed[i] == popped[j]) {
                --i;
                ++j;
            }
            ++i;
        }
        return i == 0;
    }
}